package leetcode.Hot100;

import java.util.Arrays;

/**
 * @author Cheng Jun
 * Description: 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
 * <p>
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
 * <p>
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/11/27 11:41
 * 0 <= k <= 100
 * 0 <= prices.length <= 1000
 * 0 <= prices[i] <= 1000
 */
public class maxProfit4 {
    public static void main(String[] args) {
        System.out.println(maxProfit(2, new int[]{3, 2, 6, 5, 0, 3}));
    }

    // 动态规划的状态定义：要考虑prices 数组，要考虑一共有多少次交易机会，还要考虑第i天结束时，手上是否持有股票
    // buy[i][j] 表示 第i天结束时，进行了j次交易，手上持有股票的收益
    // sell[i][j] 表示 第i天结束时，进行了j次交易，手上没有股票的收益
    // 转移方程：buy[i][j] = Math.max(buy[i-1][j], sell[i-1][j] - prices[i])
    // 转移方程：sell[i][j]  = Math.max(sell[i-1][j], buy[i-1][j-1] + prices[i])
    // 动态规划的初始值：profit[0][0] = 0, profit[0][1] = prices[0];
    static int maxProfit(int k, int[] prices) {
        int length = prices.length;
        // 不能促成一次交易的情况
        if (length == 0) {
            return 0;
        }
        // k 最大只能是 length/2
        k = Math.min(k, length / 2);
        int[][] buy = new int[length][k + 1];
        int[][] sell = new int[length][k + 1];
        buy[0][0] = -prices[0];
        sell[0][0] = 0;
        for (int i = 1; i <= k; ++i) {
            // Integer.MIN_VALUE / 2 为了防止 int类型溢出
            buy[0][i] = sell[0][i] = Integer.MIN_VALUE / 2;
        }
        for (int i = 1; i < length; i++) {
            // ？？？
            buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
            for (int j = 1; j <= k; j++) {
                buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
            }
        }
        return Arrays.stream(sell[length - 1]).max().getAsInt();
    }
}
